package c_heap.b_max_index_heap;

/**
 * 构建普通二叉堆的过程中的局限性：
 * 1. 如果元素是非常复杂的结构，例如字符串（一篇十万字的文章）等等，这样交换的代价是十分大的。不过这可以通过一些基本手段解决，
 * 2.更加致命的是元素在数组中的位置发生改变，使得在堆中很难索引到它！
 * 例如元素下标是任务ID，元素值是优先级别。当将数组构建成堆后，下标发生改变，则意味着两者无法产生联系！
 * 在原来数* 组中寻找任务只需O(1)，但是构建成堆后元素位置发生改变后需要遍历数组！所以才会引入“索引堆”这个概念。
 * <p>
 * 索引堆的性质：
 * 1.data数据初始化后位置就不再变化，同时将在堆中的索引保存到另外一个数组idx中
 * 2.发生交换的时候可以直接交换索引数据
 * 3.增加修改操作 - 可以修改data中的任意数据的值
 *
 * 索引堆的应用：
 * 索引堆是一种高级数据结构，在图算法中有广泛的应用。
 *
 * 当前索引堆的不足：
 * 1. change操作对索引交换的时候从一边进行，效率低下
 * 2. 只能从堆顶插入或删除数据
 */
@SuppressWarnings("unchecked")
public class MaxIndexBinaryHeap<Item extends Comparable<Item>> {
    private Item[] data; // 数据存储
    private int[] idx; // 数据在堆中的索引，从1开始

    private int count; // 堆中元素数量
    private int capacity; // 堆中可容纳元素数量

    public MaxIndexBinaryHeap(int capacity) {
        this.capacity = capacity;
        count = 0;
        data = (Item[]) new Comparable[capacity + 1];
        idx = new int[capacity + 1];
    }

    public MaxIndexBinaryHeap(Item[] arr) {
        capacity = arr.length;
        data = (Item[]) new Comparable[capacity + 1];
        idx = new int[capacity + 1];

        for (int i = 0; i < capacity; i++) {
            data[i + 1] = arr[i]; // 初始化数据
            idx[i + 1] = i + 1; // 初始化数据索引
        }
        count = capacity;
        for (int i = count / 2; i >= 1; i--) {
            shiftDown(i); // 对索引进行交换
        }
    }

    public int size() {
        return count;
    }

    public boolean isEmpty() {
        return count == 0;
    }

    /**
     * 插入一个新元素
     * 返回新的最大堆的元素数
     *
     * @param item
     * @return
     */
    public int unshift(Item item) {
        assert count <= capacity - 1;
        count++;
        data[count] = item;
        idx[count] = count;
        shiftUp(count); // 向上交换 - 维护最大堆的性质
        return count;
    }

    /**
     * 在索引i插入数据
     *
     * @param i    对调用者而言， 从0开始
     * @param item
     */
    public void insert(int i, Item item) {
        assert count + 1 <= capacity;
        assert (i + 1 >= 1 && i + 1 <= capacity);
        i++;
        data[i] = item;
        idx[count + 1] = i;
        count++;
        shiftUp(count);
    }

    /**
     * 最大堆中插入元素后
     * 需要逐级和父元素比较
     * 如果比父元素还大就向上进行shiftUp(向上交换数据索引)操作
     *
     * @param k 新插入元素在data中的索引
     *          新插入元素如果比父节点大就和父节点交换位置 - 维护最大堆的性质
     *          即堆中某个节点的值总是不大于其父节点的值
     */
    private void shiftUp(int k) {
        // k=1时 只有一个根元素 不存在和父元素交换数据索引
        // 只有当k>1时且k的元素比父元素k/2还大的时候才需要交换数据索引
        while (k > 1 && data[idx[k / 2]].compareTo(data[idx[k]]) < 0) {
            swapIdx(k, k / 2);
            k /= 2; // 继续向父元素进行迭代
        }
    }

    /**
     * 删除并同时返回堆顶的最大元素
     *
     * @return 堆顶元素
     * 1. 将堆顶元素和队尾元素交换
     * 2. 从堆顶元素开始进行向下交换 - 维持最大堆性质
     */
    public Item shiftItem() {
        Item ret = data[idx[1]];
        swapIdx(1, count);
        count--;
        shiftDown(1);
        return ret;
    }

    /**
     * 删除堆顶元素
     * 返回索引数组中对顶元素的索引的索引位置
     *
     * @return
     */
    public int shiftIndex() {
        assert (count > 0);
        int ret = idx[1] - 1;
        swapIdx(1, count);
        count--;
        shiftDown(1);
        return ret;
    }

    /**
     * 返回堆顶最大元素
     *
     * @return
     */
    public Item getMax() {
        assert count > 0;
        return data[idx[1]];
    }

    /**
     * @param k 向下交换的起始下标
     */
    private void shiftDown(int k) {
        while (2 * k <= count) { // 如果k有孩子 - 完全二叉树来说有左孩子就必有右孩子， 所以只需考察是否有左孩子
            int j = 2 * k; // 预设和左孩子交换
            if (j + 1 <= count && data[idx[j + 1]].compareTo(data[idx[j]]) > 0) {
                j++; // 当右孩子比左孩子大的时候 预设交换元素就改成右孩子
            }
            // 如果操作的元素已经大于或等于它最大的孩子，交换过程结束
            if (data[idx[k]].compareTo(data[idx[j]]) >= 0) break;
            // 反之 和 其最大孩子进行交换
            swapIdx(k, j);
            // 并继续考察交换后的元素的父元素 -
            k = j;

        }
    }

    private void swapIdx(int m, int n) {
        int temp = idx[m];
        idx[m] = idx[n];
        idx[n] = temp;
    }

    /**
     * 修改根据索引修改data的数据
     *
     * @param k 需要修改的数据在data的索引 - 从0开始计数
     * @param item 1. 替换data数据
     *             2. 对被修改数据的索引向上和向下交换 - 使得整个数据保持最大堆的性质
     */
    public void change(int k, Item item) {
        // 修改数据
        data[++k] = item; // data从1开始计数
        // 修改数据索引
        for (int j = 1; j <= count; j++) {
            if (idx[j] == k) { // 找到k在数据索引中的位置
                shiftUp(j);
                shiftDown(j);
                return;
            }
        }

    }

    /**
     * 打印测试
     */
    public void printHeapDataTest() {
        if (count == 0) {
            System.out.println("该堆中不包含任何数组");
            return;
        }
        if (size() >= 100) {
            System.out.println("该测试方法只能打印不超过100个容量的堆的树形结构");
            return;
        }
        if (!(data[1] instanceof Integer)) {
            System.out.println("该测试方法只能处理整数数据");
            return;
        }

        System.out.print("INDX[" + size() + "] : ");
        for (int i = 1; i <= size(); i++) {
            System.out.print((idx[i] - 1) + " ");
        }
        System.out.print("\n");
        System.out.print("DATA[" + size() + "] : ");
        for (int i = 1; i <= size(); i++) {
            System.out.print(data[i] + " ");
        }
        System.out.print(" |MAX| " + " -> " + getMax());
        System.out.print("\n===================================================\n");
    }

    /**
     * 打印测试
     * 依次出队， 从大到小打印
     */
    public void printHeapDescSortedTest() {
        int len = size();
        System.out.print("HEAP[" + len + "] : ");
        for (int i = 0; i < len; i++) {
            Item item = shiftItem();
            System.out.print(item + " ");
        }
        System.out.print(" <-- sorted desc \n");
    }

    /**
     * 打印测试
     * 传入原数组， 返回从小到大排序好的数组
     * 同时打印测试输出
     */
    public void printHeapAscSortedTest() {
        int len = size();
        Comparable[] ret = new Comparable[len];
        for (int i = len - 1; i >= 0; i--) {
            ret[i] = shiftItem();
        }
        System.out.print("HEAP[" + len + "] : ");
        for (int i = 0; i < len; i++) {
            System.out.print(ret[i] + " ");
        }
        System.out.print(" <-- sorted asc \n");
    }

    public static void main(String[] args) {
        MaxIndexBinaryHeap<Integer> maxHeap = new MaxIndexBinaryHeap<>(100);
        for (int i = 0; i < 15; i++) {
            int num = (int) (Math.random() * 100);
//            maxHeap.insert(maxHeap.size(),num);
            maxHeap.unshift(num);
            maxHeap.printHeapDataTest();
        }
        maxHeap.printHeapDescSortedTest(); // 打印完后数组清空


        Comparable[] arr = {3, 2, 5, 4, 1, 0, 21, 52, 12, 64, 2};
        MaxIndexBinaryHeap maxheap2 = new MaxIndexBinaryHeap(arr);
        System.out.println(maxheap2.count);
        maxheap2.printHeapAscSortedTest();


        MaxIndexBinaryHeap maxheap3 = new MaxIndexBinaryHeap(arr);
        maxheap3.printHeapDataTest();
        maxheap3.change(0,99);
        maxheap3.printHeapDataTest();
    }
}